【编译原理】03语法分析 | 您所在的位置:网站首页 › 文法g[n] › 【编译原理】03语法分析 |
1,语法分析的若干问题
1.1 语法分析器的作用
编译器前端的重要组成部分: (1) 根据词法分析器提供的记号流,为语法正确的输入构造分析树(或语法树)。 (2) 检查输入中的语法(可能包括词法)错误,并调用出错处理器进行适当处理。 语法分析器: 1、通用的语法分析方法 Cocke-Younger-Kasami算法和Earley算法 2、自上而下 对任何输入串,试图用一切可能的办法,从文法开始符号(根结点)出发,自上而下地为输入串建立一棵语法树;或者说为输入串寻找一个最左推导。 3、自下而上 自上而下的一般方法: 消除左递归 提取左因子 递归下降分析 预测分析器 ![]() 语法错误 词法错误:非法字符或关键字、标识符拼写错误等 语法错误:语法结构出错,如少分号、{/}不配对等 语义错误 静态语义错误涉及的是编译时可检查出来的错误,如类型不一致、参数不匹配等; 动态语义错误一般是指程序运行时的逻辑错误,如无穷递归、变量为零时作除数等。 大多数错误的诊断和恢复集中在语法分析阶段,一个原因是大多数错误是语法错误,另一个原因是语法分析方法的准确性,它们能以非常有效的方法诊断语法错误。在编译的时候,想要准确地诊断语义或逻辑错误有时是很困难的。 1.2.2.语法错误处理的目标① 清楚而准确地报告错误的出现,地点正确、不漏报、不错报也不多报; ② 迅速地从每个错误中恢复过来,以便分析继续进行; ③ 对语法正确源程序的分析速度不应降低太多。 1.2.3.语法错误的基本恢复策略希望编译器的语法分析方式不是遇到一个语法错误就停止,就需要采取某种恢复策略,使得分析在遇到错误时还能够继续进行。 紧急方式恢复:这是最简单的方法,适用于大多数分析方法。 短语级恢复:建立在产生式(CFG)的基础上,以短语为基本分析单元,同时也便于进行语法制导翻译,恢复得比紧急方式要精确,因此被认为是一种较为理想的恢复方式。 出错产生式 全局纠正 例题: 下述两条是有语法错误的语句,其中第一条赋值句结束时忘记加分号:x = a + b y = c + d; 紧急方式: x = a + b + d; -- 丢弃b之后的若干记号,直到遇到同步记号+ 短语级恢复:x = a + b; -- 加入分号,使之成为一个赋值句 2,上下文无关文法(CFG) 2.1 CFG的定义与表示 2.1.1 定义定义3.1 上下文无关文法是一个四元组G =(N,T,P,S): ① N是非终结符的有限集合(Nonterminals); ② T是终结符的有限集合(Terminals),且N∩T=Φ; ③P是产生式的有限集合(Productions),每个产生式形如: A→α,其中A∈N,被称为产生式的左部,α∈(N∪T)*,被称为产生式的右部,若α=ε,则称A→ε为空产生式(也可以记为A →); ④ S是非终结符,被称为文法的开始符号(Start symbol)。 2.2.2 例题:定义简单算术表达式的上下文无关文法G3.1=(N,T,P,S)如下所示。 N={E} T={+,*,(,),–,id} S=E P: E → E + E (1) E → E * E (2) E → (E) (3) E → –E (4) E → id (5) 2.2.3 表示1.由产生式集表示CFG 文法可以由其产生式集P代替,而不写四元组。CFG的产生式表示也被称为巴克斯范式(BNF),值得注意的是,规范的BNF中,“→”用“::=”表示。 2.产生式的一般读法: 一般情况下,可以将产生式中的记号“→”读作“定义为”或者“可导出”。 3.终结符与非终结符书写上的区分 本教材默认采用区分大小写的方法来区分终结符与非终结符,若不作特殊说明,一般用大写英文字母A、B、C表示非终结符,小写英文字母a、b、c表示终结符,小写希腊字母α、β、δ表示任意的文法符号序列,即大小写混合的英文字母串。 4.产生式的缩写形式 2.2.2的例题 G3.1可以重写为如下形式:E → E + E | E * E | (E) | –E | id 2.2 CFG产生语言的基本方法 —— 推导 2.2.1 推导定义以及性质通过推导可以产生CFG所描述的语言。 推导就是从文法的开始符号S开始,反复使用产生式,将产生式左部的非终结符替换为右部的文法符号序列,直到得到一个终结符序列 文法G(E): E → E + E (1) E→ E * E (2) E → (E) (3) E → –E (4) E → id (5) 根据文法G使用最左推导得出终结符序列 ”–(id+id)” 。 定义3.3 由CFG G所产生的语言L(G)被定义为: L(G)称为上下文无关语言(CFL),ω称为句子。若S 定义3.4 在推导过程中,若每次直接推导均替换句型中最左边的非终结符,则称为最左推导,由最左推导产生的句型被称为左句型。
类似地,可以定义最右推导与右句型,最右推导也被称为规范推导。 2.3 推导、分析树与语法树定义3.5 对CFG G的句型,分析树被定义为具有下述性质的一棵树。 ① 根由开始符号所标记; ② 每个叶子由一个终结符、非终结符或ε标记; ③ 每个内部结点由一个非终结符标记; ④ 若A→X1X2...Xn是一个产生式,则X1,X2,...,Xn是标记为A的内部结点从左到右所有孩子的标记。若A→ε,则标记为A的结点可以仅有一个标记为ε的孩子。 分析树与文法和语言存在下述关系: ① 每一直接推导(或者每个产生式),对应一棵仅有父子关系的子树,即产生式左部非终结符“长出”右部的孩子; ② 分析树的叶子从左到右,构成G的一个句型。若叶子仅由终结符标记,则构成一个句子。 分析树与推导的关系: ① 分析树是推导的图形表示,但不能显示推导的顺序; ② 每棵分析树都可以对应惟一的最左推导或最右推导;但每个句子(产生式)不一定只有一棵分析树,也就是说每个句子不一定只有一个最左推导或者最右推导。 例:句子id + id * id 例题: 用文法G采用最左推导产生句子id+id*id. ![]() 定义3.7 若文法G对同一个句子产生不止一棵分析树,则称G是二义的。 ① 一个句型有多于一棵分析树,仅与文法和句型有关,与采用的推导方法无关; ② 造成二义性的原因,是文法中缺少对文法符号优先级和结合性的规定。 在任何一个程序设计语言中,如果出现了二义性,则表示同一段程序在确定的、相同的环境下反复执行,会得到不同的结果,而这种情况在程序设计中是不允许的。也就是说,任何一个程序设计语言不应该有二义性。 2.4.2 为文法符号规定优先级和结合性改写文法可以解决二义性问题,但不是唯一的解决方法。比较上述讨论过的二义文法和非二义文法,发现二义文法至少有两个优点: ① 比非二义文法容易理解; ② 分析效率高(分析树低,直接推导步骤少)。 3,语言与文法简介到目前为止,我们在两个层面上讨论了程序设计语言的结构:从词法分析的层面上看,语言是由字母组成的记号的集合;从语法分析的层面上看,语言是由记号组成的句子的集合。记号可以用正规式描述,句子可以用CFG描述。 程序设计语言的结构均可以用文法来描述。文法无论对程序设计语言的设计还是对编译器的编写,至少在以下三个方面起着重要作用: ① 文法给出了精确的、易于理解的语言结构的说明; ② 以文法为基础的语言,便于加入新的或修改、删除旧的语言结构; ③ 有些类别的文法,可以自动生成高效的分析器。 3.1.为什么用正规式而不用CFG描述程序设计语言的词法根据推论3.1,CFG既描述程序设计语言的语法又描述词法,而基于下述几个原因,往往采用正规式而不是CFG描述词法: ① 词法规则简单,用正规式描述已足够; ② 正规式的表示比CFG更直观、简洁、易于理解; ③ 有限自动机的构造比下推自动机简单,且分析效率高; ④ 区分词法和语法,为编译器前端的模块划分提供方便。 3.2 正规式和CFG的适用条件一般情况下,正规式适合描述线性结构,如标识符、关键字、注释等。而CFG适合描述具有嵌套(层次)性质的非线性结构,如不同结构的句子if-then-else、begin-end等。 3.3 形式语言与自动机简介乔姆斯基(Chomsky)把文法分为四种类型: 0型、1型、2型和3型。文法之间的差异在于对产生式施加不同的限制。 定义3.8 若文法G=(N,T,P,S)的每个产生式α→β中,均有α∈(N∪T)*,且至少含有一个非终结符,β∈(N∪T)*,则称G为0型文法。 对0型文法施加以下第i条限制,即可得到i型文法。 1.G的任何产生式α→β(S→ε除外) 均满足|α|≤|β| (|x|表示x中文法符号的个数); 2.G的任何产生式形如A→β,其中A∈N,β∈(N∪T)*; 3.G的任何产生式形如A→a 或者A→aB(或者A→Ba),其中A,B∈N,a∈T。 0型文法也被称为短语文法,任何0型语言都是递归可枚举的,反之,递归可枚举集也必定是一个0型语言。 1型文法就是上下文有关文法,这种文法意味着对非终结符的替换必须考虑上下文,并且一般不允许换成ε串。例如,若αAβ→αγβ是1型文法的产生式,α和β不全为空,则非终结符A只有在左边是α,右边是β这样的上下文中才可能替换成γ。 2型文法就是上下文无关文法,非终结符的替换无需考虑上下文。 3型文法等价于正规式,因而也被称为正规文法或线性文法。 四种类型的文法和它们所描述的语言,以及识别对应语言的自动机分别列举在表中。 自上而下分析的基本思想是:对于任何一个输入序列,从文法的开始符号开始,进行最左推导,直到得到一个合法句子或者发现一个非法结构。在推导的过程中试图用一切可能的方法,自上而下、从左到右为输入序列建立分析树。整个分析是一种试探的过程,是反复使用不同产生式谋求与输入序列匹配的过程。 4.2 例题已知如下文法G(S),给出输入序列ω=cad,自上而下试探建立分析树的过程。 G(S): S → cAd A → ab | a ![]() (1) 若存在形如A → αβ1|αβ2的产生式,即A产生式中有多于一个候选项的前缀相同(称为公共左因子,或简称左因子),则可能会造成虚假匹配,使得在分析过程中可能需要进行大量回溯,从而造成分析效率低、语义动作难以恢复以及出错位置的报告不确切等。 (2) 若存在形如A → Aα的产生式,则分析过程中一旦采用了该产生式去替换,就会陷入死循环而使分析无法进行下去。产生式的这种形式被称为左递归。 为了避免上述弱点,需要对文法进行重写。消除左递归,以避免陷入死循环;提取左因子,以避免回溯。 4.3 消除左递归分类:直接左递归 间接左递归 规则1 直接左递归的产生式A→Aα|β (β不以A开头), A→βA' A'→αA'|ε 规则2 直接左递归的产生式 A→ Aα1 | Aα2 | ... | Aαm |β1 |β2 | ...|βn(所有βi均不以A直接开头或间接开头), A→β1A'|β2A'|...|βnA' A'→α1A'|α2A'|...αmA'|ε 并不是所有的文法都能消除左递归!!! 4.4 提取左因子对于有左因子的文法,推导过程中会出现无法确定用A产生式的哪个候选项替换A的情况,这时,可以重写A产生式来推迟这种决定,直到看见足够的输入,能正确决定所需选择为止。这一过程类似于有限自动机的确定化,被称为提取左因子。 算法3.3 提取文法的左因子 输入 : 文法G 输出: 等价的无左因子文法G' 方法 :为每个产生式A,找出其候选项中最长公共前缀α,重排A产生式如下,其中γ是不以α为前缀的其他候选项。 A→ αβ1|αβ2| ...|αβn|γ 并用下述产生式替代之。 A→ αA'|γ A'→ β1|β2| ...|βn 重复此过程,直到所有A产生式的候选项中均不再有公共前缀。 练习: 1、文法G(A):A→aABj | a B→Bb | d 2、文法G(M):M→MaH | H H→b(M) | (M) | b 3、文法G(S):S→AdD | ε A→aAd | ε D→DdA | b | ε 5,FIRST集和FOLLOW集算法3.5 计算X的FIRST集合 输入 文法符号X 输出 X的FIRST集合 方法 应用下述规则: ① 若X是终结符,则FIRST(X)={X}; ② 若X 是非终结符且有X→ε,则加入ε到FIRST(X); ③ 若X 是非终结符且有X→Y1Y2...Yk,并令Y0=ε,Yk+1=ε,则对所有j(0≤j≤k),若a∈FIRST(Yj+1)且ε∈FIRST(Yj),加入a到FIRST(X)。 算法3.6 计算所有非终结符的FOLLOW集合 输入 文法G 输出 G中所有非终结符的FOLLOW集合 方法 应用下述规则: ① 加入#到FOLLOW(S),其中,S是开始符号,#是输入结束标记; ② 若有产生式A→αBβ,则除ε外,FIRST(β)的全体加入到FOLLOW(B); ③ 若有产生式A→αB或A→αBβ而ε∈FIRST(β),则FOLLOW(A)的全体加入FOLLOW(B)。 算法3.7 构造预测分析表 输入 文法G 输出 分析表M 方法 应用下述规则: ① 对文法的每个产生式A→α,执行②和③; ② 对FIRST(α)的每个终结符a,加入α到M[A,a]; ③ 若ε在FIRST(α)中,则对FOLLOW(A)的每个终结符b(包括#),加入α到M[A,b]; ④ M中其他没有定义的条目均是error。 预测分析表是一个二维数组M[A, a] 所有的非终结符构成分析表的行下标; 所有的终结符构成分析表的列下标,其中包括特殊的结束标志#。 M[A, a]中的内容表示当前栈顶为非终结符A且当前输入为终结符a时,分析器要进行的动作。 3.4.5.3 LL(1)文法 定义3.12 一个文法G被称为是LL(1)文法,当且仅当为它构造的预测分析表中不含多重定义的条目。由此分析表所组成的分析器被称为LL(1)分析器,它所分析的语言被称为LL(1)语言。第一个L表示从左到右扫描输入序列,第二个L表示产生最左推导,1表示在确定分析器的每一步动作时向前看一个终结符。 推论3.2 一个文法G是LL(1)的,当且仅当G的任何两个产生式A→α|β,满足下面条件: ① 对任何终结符a,α和β不能同时推导出以a开始的文法符号序列; ② α和β最多有一个可以推导出ε; ③ 若β ε,则α不能推导出以在FOLLOW(A)中的终结符开始的任何文法符号序列。 推论3.2实际上等价于当且仅当G的任何两个产生式A→α|β满足上述三个条件时,为文法G构造的预测分析表中不含多重定义的条目。反之,若不满足三个条件之一,则分析表中有多重定义条目。 若条件①不满足,即存在终结符a,α和β同时推导出以a开始的文法符号序列,则根据算法3.7规则②,M[A,a]中就会有多重定义条目A→α和A→β; 若条件②不满足,即α和β均可推出ε,则根据算法3.7规则③,任何属于FOLLOW(A)的终结符b(包括#),M[A,b]中就会有多重定义条目A→α和A→β; 若条件③不满足,即存在终结符b,它既在FOLLOW(A)中,又在FIRST(α)中,则 算法3.7规则②把条目A→α加入到M[A,b]中,而规则③又把条目A→β加入到M[A,b]中。 LL(1)文法的弱点: (1) 文法比较难写。因为按照人们习惯写出的文法,往往含有左递归和左因子。虽然有成熟的算法可以消除左递归和提取左因子,但改写之后的文法很难读也很难使用。同时对比分析树可以看出,改写后文法构造的分析树不直观且推导步骤增加。 (2) LL(1)文法适应范围有限,对于有些语言,往往写不出它的LL(1)文法。 |
CopyRight 2018-2019 实验室设备网 版权所有 |